#include <bits/stdc++.h>

using namespace std;
using ll = long long;

template <typename VecT>
vector<VecT> convex_hull(vector<VecT> veces)
{
    vector<VecT> ans;
    vector<int> stk;
    vector<bool> used(veces.size());

    sort(veces.begin(), veces.end(), [](VecT a, VecT b)
         {
            if(a.x == b.x)
            return a.y < b.y;
        return a.x < b.x; });

    for (int i = 0; i < veces.size(); i++)
    {
        while (stk.size() >= 2 && ((veces[stk[stk.size() - 1]] - veces[stk[stk.size() - 2]]) % (veces[i] - veces[stk[stk.size() - 1]])).z <= 0)
        {
            used[stk[stk.size() - 1]] = false;
            stk.pop_back();
        }

        used[i] = true;
        stk.push_back(i);
    }
    int tmp = stk.size();

    for (int i = veces.size() - 1; i >= 0; i--)
    {
        if (used[i] && i != 0)
            continue;
        while (stk.size() > tmp && ((veces[stk[stk.size() - 1]] - veces[stk[stk.size() - 2]]) % (veces[i] - veces[stk[stk.size() - 1]])).z <= 0)
            stk.pop_back();
        if (i != 0)
            stk.push_back(i);
    }

    for (int i : stk)
        ans.push_back(veces[i]);

    return ans;
}
